/**
 *
 * 560. 和为K的子数组
 *
 * 给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
 *
 */

 // 解法一：前缀和+暴力法。耗时较长o(n^2)
func subarraySum(nums []int, k int) int {
    pre_sum:= make([]int, len(nums)+1)

    for i:=1;i<len(pre_sum);i++ {
        pre_sum[i] = pre_sum[i-1]+nums[i-1]
    }

    ans := 0

    for i:=0;i<len(pre_sum);i++ {
        for j:=i+1;j<len(pre_sum);j++ {
            if pre_sum[j]-pre_sum[i] == k {
                ans++
            }
        }
    }
    return ans
}

// 解法二：前缀和+哈希表 o(n)
func subarraySum(nums []int, k int) int {
    count_map := make(map[int]int)
    count_map[0] = 1
    sum :=0
    count:=0
    for i:=0;i<len(nums);i++ {
        sum+=nums[i]
        if val,ok:=count_map[sum-k]; ok {
            count+=val
        }
        count_map[sum]++
    }
    return count
}